package com.gxc.attempt;

/**
 * 有n个打包机器从左到右一字排开，上方有一个自动装置会抓取一批放物品到每个打包机上，
 * 放到每个机器上的这些物品数量有多有少，由于物品数量不相同，需要工人将每个机器上的物品进行移动从而到达物品数量相等才能打包。
 * 每个物品重量太大、每次只能搬一个物品进行移动，为了省力，只在相邻的机器上移动。
 * 请计算在搬动最小轮数的前提下，使每个机器上的物品数量相等。
 * 如果不能使每个机器上的物品相同返回-1。
 * 例如[1,0,5]表示有3个机器，每个机器上分别有1、0、5个物品，经过这些轮后:
 * 第一轮:1 0<-5=> 114
 * 第二轮:1<-1<- 4 => 213
 * 第三轮:21<3=>222
 * 移动了3轮，每个机器上的物品相等，所以返回3
 * 例如[2.2.3]表示有3个机器，每个机器上分别有2、2、3个物品，
 * 这些物品不管怎么移动，都不能使三个机器上物品数量相等，返回-1。
 *
 * 解法：
 * 1.先尝试总数/机器数量，是否能被整除，如果不能整除，返回-1
 * 2.尝试以当前位置为划分点，分左右两个部分，确认左部分，当前位置，右部分，各自需要增加和减少的数量，求取每个位置的移动数量，最大值就是需要移动的数量
 *
 * 假设衣服的总数量是k个，那么如果m不能被k整除，则返回-1。
 * 如果可以被整除，那么m/k就是每台洗衣机需要的数量，每台洗衣机现在实际有的数量可能多也可能少，
 * 我们假设现在来到了第i台洗衣机(最前面的洗衣机为第1台)，分以下情况进行讨论
 * i前面的i-1台洗衣机所需的数量(i-1) * m/k大于它们所拥有的实际数量，差值为a。i后面的n-i台洗衣机所需的数量(n-i) * m/k大于它们所拥有的实际数量，
 * 差值为b。
 * 那么此时一定是第i台洗衣机多了abs(a)+abs(b)件衣服，因为每次只能移动一件衣服，
 * 所以至少需要abs(a)+abs(b)步才能满足要求
 * i前面的i-1台洗衣机所需的数量(i-1) * m/k小于它们所拥有的实际数量，差值为a。i后面的n-i台洗衣机所需的数量(n-i) * m/k小于它们所拥有的实际数量，
 * 差值为b。
 * 那么此时一定是第i台洗衣机少了abs(a)+abs(b)件衣服，因为每次可以接收两件衣服，
 * 所以至少需要max{abs(a),abs(b)}步才能满足要求
 * i前面的i-1台洗衣机所需的数量(i-1) * m/k小于它们所拥有的实际数量，差值为a。i后面的n-i台洗衣机所需的数量(n-i) * m/大于它们所拥有的实际数量，
 * 差值为b。那么此时是左边多了abs(a)件，右边少了abs(b)件衣服，abs(a)与abs(b)哪个大哪个需要的步数就多，
 * 此时至少需要max{abs(a),abs(b)}步才能满足要求、
 * 左边少右边多的情况同3理
 */
public class PackingMachine {

    public static void main(String[] args) {
        int size = 1000;
        for (int i = 0; i < size; i++) {
            int[] randomArray = random();
            if (move(randomArray)!=move2(randomArray)) {
                for (int j = 0; j < randomArray.length; j++) {
                    System.out.print(randomArray[j] + " ");
                }
                System.out.println("算法错误");
                break;
            }
        }

        System.out.println("------------");
        int[] array = new int[]{1 ,77 ,36};
        System.out.println(move(array));
        System.out.println(move2(array));

    }


    /**
     * 尝试以当前位置为划分点，分左右两个部分，确认左部分，当前位置，右部分，各自需要增加和减少的数量，
     * 求取每个位置的移动数量，最大值就是需要移动的数量
     * @param array
     * @return
     */
    public static int move(int[] array) {
        if (array == null || array.length==0) return 0;
        int sum = 0;
        for (int i = array.length - 1; i >= 0; i--) {
            sum += array[i];
        }
        //先尝试总数/机器数量，是否能被整除，如果不能整除，返回-1
        if (sum%array.length!=0) return -1;
        //平均值（总数/机器数量）
        int average = sum/array.length;

        int max = Integer.MIN_VALUE;
        int leftPart = 0;
        int step = 0;
        for (int i = 0; i < array.length; i++) {
            step = process(leftPart, array[i], sum-leftPart-array[i], average * i,average, sum - average*i- average);
            leftPart += array[i];
            max = Math.max(step, max);
        }
        return max;
    }

    /**
     *
     * @param leftPart  左部分
     * @param cur       当前位置
     * @param rightPart 右部分
     * @return
     */
    private static int process(int leftPart, int cur, int rightPart, int leftAverage, int average, int rightAverage) {
        //如果当前位置数量大于平均值
        if (cur > average) {
            return Math.max(cur-average, Math.max(Math.abs(leftPart - leftAverage), Math.abs(rightPart - rightAverage)));
            //如果当前位置数量小于平均值
        } else if (cur < average) {
            return Math.max(Math.abs(leftPart - leftAverage), Math.abs(rightPart - rightAverage));
        } else {
            return Math.max(Math.abs(leftPart - leftAverage), Math.abs(rightPart - rightAverage));
        }
    }

    public static int move2(int[] array) {
        if (array == null || array.length==0) return 0;
        int sum = 0;
        for (int i = array.length - 1; i >= 0; i--) {
            sum += array[i];
        }
        //先尝试总数/机器数量，是否能被整除，如果不能整除，返回-1
        if (sum%array.length!=0) return -1;
        //平均值（总数/机器数量）
        int average = sum/array.length;

        int max = Integer.MIN_VALUE;
        int leftPart = 0;
        int step = 0;
        for (int i = 0; i < array.length; i++) {
            step = process2(leftPart-average * i, sum-leftPart-array[i] - (sum - average*i- average));
            leftPart += array[i];
            max = Math.max(step, max);
        }
        return max;
    }

    private static int process2(int leftNeed, int rightNeed) {
        //如果当前位置数量大于平均值
        if (leftNeed <0 && rightNeed<0) {
            return Math.abs(leftNeed) + Math.abs(rightNeed);
            //如果当前位置数量小于平均值
        } else {
            return Math.max(Math.abs(leftNeed), Math.abs(rightNeed));
        }
    }

    private static int[] random() {
        int size = (int) (100 * Math.random());
        int[] array = new int[size];
        for (int i = 0; i < array.length; i++) {
            array[i] = (int) (100 * Math.random());
        }
        return array;
    }

}
